package T2560;

public class Main {
}
class Solution {
    public int minCapability(int[] nums, int k) {
        int max = nums[0];
        int min = nums[0];
        for (int i = 1; i < nums.length; i++) {
            max = Math.max(nums[i], max);
            min = Math.min(nums[i], min);
        }
        int n = nums.length;
        int ans = 0;
        int mid = 0;
        while (min <= max) {
            mid = min + ((max - min) >> 1);
            // System.out.println("中间值: "+mid);
            // System.out.println("最大值: "+max);
            // System.out.println("最小值: "+min);
            // System.out.println(f1(nums, mid, n));

            if (f1(nums, mid, n) >= k) {
                ans = mid;
                max = mid - 1;
            } else {
                min = mid + 1;
            }
        }
        return ans;
    }

    private int f1(int[] nums, int k, int n) {
        if (n == 1) {
            return ((nums[0] <= k) ? 1 : 0);
        }
        if (n == 2) {
            return (nums[0] <= k || nums[1] <= k) ? 1 : 0;
        }
        int[] count = new int[n];
        count[0] = ((nums[0] <= k) ? 1 : 0);
        count[1] = (nums[0] <= k || nums[1] <= k) ? 1 : 0;
        for (int i = 2; i < n; i++) {
            count[i] = Math.max(count[i - 1], ((nums[i] <= k ? 1 : 0) + count[i - 2]));
        }
        return count[n - 1];
    }
}
